home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ddj0897.zip / DYN401.ZIP / class / memalloc.d < prev    next >
Text File  |  1996-08-25  |  7KB  |  331 lines
  1.  
  2. /*
  3.  *
  4.  *    Copyright (c) 1993-1996 Algorithms Corporation
  5.  *    3020 Liberty Hills Drive
  6.  *    Franklin, TN  37067
  7.  *
  8.  *    ALL RIGHTS RESERVED.
  9.  *
  10.  *
  11.  *
  12.  */
  13.  
  14.  
  15. /*  This really just a .c file but is copied to a .d file in case someone
  16.     removes all the .c files from the class directory.  Just copy it to
  17.     memalloc.c
  18. */
  19.  
  20. /*  Reasonably fast memory allocator which reduces fragmentation and has
  21.     the ability to compact used memory.  */
  22.  
  23. #include "dynl.h"
  24. #include <string.h>
  25. #include "memalloc.h"
  26.  
  27.  
  28. typedef    struct  _header  {
  29.     char    status;        /*  Used/Free/ **froZen**    */
  30.     struct    _header    *next;    /*  Next free header or pointer to pointer
  31.                     using this memory block    */
  32.     unsigned  rsize;    /*  request size        */
  33.     unsigned  size;        /*  mem size            */
  34. /*    char    mem[];            Actual memory size varys    */
  35. }    Header;
  36.  
  37. typedef    struct  _memBlk  {
  38.     struct    _memBlk    *next;
  39.     unsigned    size;    /*  size of h block          */
  40. /*    Header    h[];            Actual size vary        */
  41. }    MemBlk;
  42.  
  43.  
  44. typedef    struct    {
  45.     unsigned  userBytes;    /*  minimum user bytes per header    */
  46.     Header    *h;        /*  pointer to first free header    */
  47. }    MAP;
  48.  
  49. #define SZ(x)    (sizeof(Header)*x)
  50.  
  51. #define RND(n)    (((n-1) / sizeof(Header)) + 1) * sizeof(Header);
  52.  
  53. static    MAP    Map[] = {
  54.     {SZ(1)}, 
  55.     {SZ(2)}, 
  56.     {SZ(4)}, 
  57.     {SZ(8)}, 
  58.     {SZ(16)}, 
  59.     {SZ(32)}, 
  60.     {SZ(64)}, 
  61.     {SZ(128)}, 
  62.     {SZ(256)}, 
  63.     {SZ(512)}, 
  64.     {SZ(1024)}, 
  65.     {SZ(2048)}, 
  66.     {0}
  67. };
  68.  
  69.     
  70.     
  71. static    MemBlk    *MMBP = NULL;        /*  master memory block pointer  */
  72.  
  73. static    unsigned    DBS = 1024;    /*  Default block size     */
  74.  
  75. static    void    more_core(unsigned);
  76. static    Header    *compact(MemBlk *);
  77.  
  78. static    CRITICALSECTION    CS;
  79. static    int    CS_init = 0;
  80.  
  81. void    *MA_malloc(unsigned n, void *p)
  82.                 /*  requested size  */
  83.                /*  pointer to variable which will hold the return value  */
  84. {
  85.     unsigned  sz;    /*  rounded size needed        */
  86.     int    i;    /*  map index            */
  87.     Header    *h;    /*  header            */
  88.     Header    *ph;    /*  previous header        */
  89.     Header    *bh;    /*  best header            */
  90.     Header    *pbh;    /*  previous best header    */
  91.     unsigned tnb;    /*  total number of blocks    */
  92.     unsigned nbn;    /*  number of blocks needed    */
  93.     unsigned nbl;    /*  number of blocks left    */
  94.  
  95.     if (!CS_init) {
  96.         INITIALIZECRITICALSECTION(CS);
  97.         CS_init = 1;
  98.     }
  99.     ENTERCRITICALSECTION(CS);
  100.     if (!n)
  101.         ++n;
  102.     sz = RND(n);
  103.  
  104.     /*  find starting bucket  */
  105.     for (i=1 ; Map[i].userBytes  &&  Map[i].userBytes <= sz ; ++i);
  106.     i--;
  107.     
  108.  
  109.     /*  find best fit  */
  110.     for (bh=pbh=ph=NULL, h=Map[i].h ; h ; ph=h, h=h->next)
  111.         if (h->size == sz)  {  /*  exact match  */
  112.             if (ph)
  113.                 ph->next = h->next;
  114.             else
  115.                 Map[i].h = h->next;
  116.             h->status = 'U';
  117.             h->next = (Header *) p;
  118.             h->rsize = n;
  119.             LEAVECRITICALSECTION(CS);
  120.             return h+1;
  121.         } else if (h->size > sz  &&  (!bh  ||  bh->size > h->size))  {
  122.             pbh = ph;
  123.             bh = h;
  124.         }
  125.     /*  exact match not found - use best fit if found  */
  126.     if (bh)  {
  127.         if (pbh)
  128.             pbh->next = bh->next;
  129.         else
  130.             Map[i].h = bh->next;
  131.         bh->status = 'U';
  132.         bh->next = (Header *) p;
  133.         bh->rsize = n;
  134.         LEAVECRITICALSECTION(CS);
  135.         return bh+1;
  136.     }
  137.  
  138.  
  139.     /*  find a block in any larger block  */
  140.     for (i++ ; Map[i].userBytes  &&  !Map[i].h ; ++i);
  141.  
  142.     if (!Map[i].userBytes)  {   /*  no block large enough at all  */
  143.         more_core(n);
  144.         LEAVECRITICALSECTION(CS);
  145.         return MA_malloc(n, p);
  146.     }
  147.  
  148.     /*  larger than necessary block found - split  */
  149.  
  150.     /*  unlink block to be used  */
  151.  
  152.     h = Map[i].h;
  153.     Map[i].h = h->next;
  154.  
  155.     tnb = h->size / sizeof(Header);
  156.     nbn = sz / sizeof(Header);
  157.     nbl = tnb - nbn;
  158.     if (nbl > 5)  {
  159.         bh = h + (nbn + 1);    /*  remainder        */
  160.         bh->status = 'U';    /*  make believe    */
  161.         bh->next = NULL;
  162.         bh->rsize = bh->size = (nbl - 1) * sizeof(Header);
  163.         h->size -= nbl * sizeof(Header);
  164.         MA_free(bh+1);
  165.     }
  166.     h->status = 'U';
  167.     h->next = (Header *) p;
  168.     h->rsize = n;
  169.     LEAVECRITICALSECTION(CS);
  170.     return h+1;
  171. }
  172.  
  173. void    *MA_calloc(unsigned n, void *p)
  174. {
  175.     p = MA_malloc(n, p);
  176.     memset(p, 0, n);
  177.     return p;
  178. }
  179.  
  180. void    MA_free(void *arg)
  181. {
  182.     int    i;
  183.     Header    *h = (Header *) arg;
  184.  
  185.     ENTERCRITICALSECTION(CS);
  186.     if (!h  ||  (--h)->status != 'U') {
  187.         LEAVECRITICALSECTION(CS);
  188.         return;
  189.     }
  190.  
  191.     /*  find bucket  */
  192.     for (i=1 ; Map[i].userBytes  &&  Map[i].userBytes <= h->size ; ++i);
  193.     i--;
  194.  
  195.     h->status = 'F';
  196.     if (h->next)
  197.         *((char **) h->next) = NULL;
  198.     h->next = Map[i].h;
  199.     Map[i].h = h;
  200.     LEAVECRITICALSECTION(CS);
  201. }
  202.  
  203. static    void    more_core(unsigned n)
  204. {
  205.     unsigned  sz;    /*  memory area needed        */
  206.     unsigned  as;    /*  allocation size        */
  207.     MemBlk     *mb;
  208.     Header     *h;
  209.  
  210.     sz = n > DBS ? n : DBS;
  211.     sz = RND(sz);
  212.     as = sizeof(MemBlk) + sizeof(Header) + sz;
  213.     mb = (MemBlk *) malloc(as);
  214.     if (!mb)  {
  215.         fprintf(stderr, "\nOut of memory.\n");
  216.         exit(1);
  217.     }
  218.     mb->next = MMBP;
  219.     MMBP = mb;
  220.     mb->size = sz + sizeof(Header);
  221.  
  222.     h = (Header *) (mb+1);
  223.     h->status = 'U';    /*  make believe    */
  224.     h->next = NULL;
  225.     h->size = sz;
  226.     MA_free(h+1);
  227. }
  228.  
  229. void    *MA_realloc(void *arg, unsigned n)
  230. {
  231.     char    *m;
  232.     Header    *h = (Header *) arg;
  233.  
  234.     ENTERCRITICALSECTION(CS);
  235.     if (!h  ||  (--h)->status != 'U') {
  236.         LEAVECRITICALSECTION(CS);
  237.         return NULL;
  238.     }
  239.     if (h->size >= n)  {
  240.         h->rsize = n;
  241.         LEAVECRITICALSECTION(CS);
  242.         return h+1;
  243.     }
  244.     m = (char *) MA_malloc(n, h->next);
  245.     memcpy(m, h+1, h->rsize);
  246.     h->next = NULL;        /*  don't NULL out variable pointer  */
  247.     MA_free(h+1);
  248.     LEAVECRITICALSECTION(CS);
  249.     return m;
  250. }
  251.  
  252.  
  253. void    MA_compact(void)
  254. {
  255.     MemBlk    *mb;
  256.     Header    *fh, *mfh = NULL;
  257.     int    i;
  258.  
  259.     ENTERCRITICALSECTION(CS);
  260.     /*  compact each memBlk   */
  261.     for (mb=MMBP ; mb ; mb = mb->next)  {
  262.         fh = compact(mb);
  263.         if (fh)  {
  264.             fh->next = mfh;
  265.             mfh = fh;
  266.         }
  267.     }
  268.     
  269.     /*  clear out free map  */
  270.     for (i=0 ; Map[i].userBytes ; ++i)
  271.         Map[i].h = NULL;
  272.  
  273.     /*  rebuild free map  */
  274.     while (fh = mfh)  {
  275.         mfh = fh->next;
  276.         fh->status = 'U';    /*  make believe  */
  277.         fh->next = NULL;
  278.         MA_free(fh+1);
  279.     }
  280.     LEAVECRITICALSECTION(CS);
  281. }
  282.  
  283. #define NEXTH(h)    (Header *) ((char *) h + (sizeof(Header)+h->size))
  284.  
  285. static    Header    *compact(MemBlk *mb)
  286. {
  287.     char    *end = (char *) (mb+1) + mb->size;
  288.     Header    *h = (Header *) (mb+1);
  289.     Header    *to, *pto=NULL;
  290.  
  291.     for (to=h ; (char *) h < end ; h = NEXTH(h))  {
  292.         if (h->status == 'F')
  293.             continue;
  294.         if (to != h)  {
  295.             memcpy(to, h, h->rsize+sizeof(Header));
  296.             if (h->next)
  297.                 *((Header **) to->next) = to + 1;
  298.         }
  299.         to->size = RND(to->rsize);
  300.         pto = to;
  301.         to = NEXTH(to);
  302.     }
  303.     if ((char *) to >= end)
  304.         return NULL;
  305.     to->status = 'F';
  306.     to->size = (end - (char *) to) - sizeof(Header);
  307.     if (!to->size)  {
  308.         if (pto)
  309.             pto->size += to->size + sizeof(Header);
  310.         return NULL;
  311.     }            
  312.     return to;
  313. }
  314.  
  315.  
  316.  
  317.  
  318.  
  319. /*
  320.  *
  321.  *    Copyright (c) 1993-1996 Algorithms Corporation
  322.  *    3020 Liberty Hills Drive
  323.  *    Franklin, TN  37067
  324.  *
  325.  *    ALL RIGHTS RESERVED.
  326.  *
  327.  *
  328.  *
  329.  */
  330.  
  331.